import java.util.HashSet;
import java.util.Set;

/**
 * @作者 钟先崟
 * @时间 2023-03-16 15:00
 * @说明 217. 存在重复元素
 * 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
 * 示例 1：
 * 输入：nums = [1,2,3,1]
 * 输出：true
 */
public class Solution {
    public static void main(String[] args) {
        System.out.println(containsDuplicate(new int[]{-100, 1, 1, 3, 4, 2}));
    }

    /**
     * 执行用时：3 ms , 在所有 Java 提交中击败了98.46%的用户
     * 内存消耗：53.4 MB, 在所有 Java 提交中击败了82.27%的用户
     *
     * @param nums
     * @return
     */
    public static boolean containsDuplicate(int[] nums) {
        int maxLen = Integer.MIN_VALUE;
        int minLen = Integer.MAX_VALUE;
        for (int x : nums) {
            if (x > maxLen) maxLen = x;
            if (x < minLen) minLen = x;
        }
        if (maxLen > 10000000 || minLen < -10000000) {
            Set<Integer> set = new HashSet<Integer>();
            for (int x : nums) {
                if (!set.add(x)) {
                    return true;
                }
            }
            return false;
        }
        int[] n = new int[maxLen + 1 - minLen];
        for (int x : nums) {
            if (n[x - minLen] != 0) return true;
            else {
                n[x - minLen] = 1;
            }
        }
        return false;
    }
}
